package owg.util;

import java.awt.Graphics;
import java.awt.Image;
import java.awt.Rectangle;
import java.awt.image.BufferedImage;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.lang.ref.WeakReference;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.Random;

import javax.imageio.ImageIO;

import owg.util.Calc;

/**
 * This is a class providing static methods for doing various common computations.
 */
public class Calc
{
	
	public final static int bytesPerByte = 1;
	public final static int bytesPerFloat = Float.SIZE / Byte.SIZE;
	public final static int bytesPerShort = Short.SIZE / Byte.SIZE;
	public final static int bytesPerInt = Integer.SIZE / Byte.SIZE;
	public static final float toRad = (float)(Math.PI/180);
	public static final float toDeg = (float)(180/Math.PI);
	public static final float PI = (float)Math.PI;
	
	private static final Random rng = new Random();
	
	/*HUBOLS USELESS CALC STUFF:*/
	/**is a within the range dictated by b and c*/
	public static boolean isContained(double a, double b, double c){
		return ((a >= b && a <= c) || (a >= c && a <= b));
	}
	
	/**this function reads a file line-by-line and returns its contents in the form of a String[] array of appropriate size*/
	public static String[] lineByLine(File f){
		ArrayList<String> output = new ArrayList<String>();
		try {
			FileReader z = new FileReader(f);
			BufferedReader r = new BufferedReader(z);
			
			String s;
			while ((s = r.readLine()) != null)
				output.add(s);
			
			z.close();
			r.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		String[] out = new String[output.size()];
		for (int i=0; i<out.length; i++)
			out[i] = output.get(i);
		
		return out;
	}
	
	public static double dirX(double len, double dir){
		return len*Math.cos(toRad*dir);
	}
	public static double dirY(double len, double dir){
		return -len*Math.sin(toRad*dir);
	}
	public static double approach(double current, double wanted, double divide){
		return current+((wanted-current)/divide);
	}
	/**return a random number from 0 - input*/
	public static double random(double input){
		return Math.random()*input;
	}
	public static Object choose(Object... entries){
		int i = (int)(Math.random()*entries.length);
		return entries[i];
	}
	public static Integer parseInt(String s){
		try{
			return Integer.parseInt(s);
		}catch(NumberFormatException e){
			return null;
		}
	}
	
	public static Double parseDouble(String s){
		try{
			return Double.parseDouble(s);
		}catch(NumberFormatException e){
			return null;
		}
	}
	
	public static Long parseLong(String s){
		try{
			return Long.parseLong(s);
		}catch(NumberFormatException e){
			return null;
		}
	}
	
	public static Boolean parseBoolean(String s){
		try{
			return Boolean.parseBoolean(s);
		}catch(NumberFormatException e){
			return null;
		}
	}
	
	/**make a hex color from three doubles dude*/
	public static String makeHexColor(double... vals){
		return ""+formatNumberString(Integer.toHexString((int)((vals[0] * 256) - 1)),2)+""+formatNumberString(Integer.toHexString((int)((vals[1] * 256) - 1)),2)+""+formatNumberString(Integer.toHexString((int)((vals[2] * 256) - 1)),2);
	}
	
	/**make a hex color from three ints (0 - 255) dude*/
	public static String makeHexColorInt(int... vals){
		return ""+formatNumberString(Integer.toHexString((int)vals[0]),2)+""+formatNumberString(Integer.toHexString((int)vals[1]),2)+""+formatNumberString(Integer.toHexString((int)vals[2]),2);
	}
	
	/**input: "20", 4; output: "0020"*/
	public static String formatNumberString(String s, int n){
		String output = s;
		while (output.length() < n)
			output = "0"+output;
		return output;
	}
	
	/**returns double ranging from -a to a*/
	public static double rangedRandom(double a){
		return -a + Calc.random(a * 2);
	}
	/**authored by Gabriel Ivăncescu*/
	public static boolean triangleCircleCollision(double centrex, double centrey, double radius, double v1x, double v1y, double v2x, double v2y, double v3x, double v3y){
		//TEST 1: Vertex within circle
		double c1x = centrex - v1x;
		double c1y = centrey - v1y;
		
		double radiusSqr = radius*radius;
		double c1sqr = c1x*c1x + c1y*c1y - radiusSqr;
		
		if (c1sqr <= 0)
			return true;
		
		double c2x = centrex - v2x;
		double c2y = centrey - v2y;
		double c2sqr = c2x*c2x + c2y*c2y - radiusSqr;
		
		if (c2sqr <= 0)
			return true;
		
		double c3x = centrex - v3x;
		double c3y = centrey - v3y;
		
		double c3sqr = c3x*c3x + c3y*c3y - radiusSqr;
		radiusSqr = c3sqr;
		
		if (c3sqr <= 0)
			return true;
		
		
		//TEST 2: Circle centre within triangle
		
		//Calculate edges
		double e1x = v2x - v1x;
		double e1y = v2y - v1y;
		
		double e2x = v3x - v2x;
		double e2y = v3y - v2y;
		
		double e3x = v1x - v3x;
		double e3y = v1y - v3y;
		
		if (e1y*c1x >= e1x*c1y && e2y*c2x >= e2x*c2y && e3y*c3x >= e3x*c3y)
			return true;
		
		
		//TEST 3: Circle intersects edge
		double k = c1x*e1x + c1y*e1y;
		
		if (k > 0){
			double len = e1x*e1x + e1y*e1y;
			
			if (k < len){
				if (c1sqr * len <= k*k)
					return true;
			}
		}
		
		//Second edge
		k = c2x*e2x + c2y*e2y;
		
		if (k > 0){
			double len = e2x*e2x + e2y*e2y;
			
			if (k < len){
				if (c2sqr * len <= k*k)
					return true;
			}
		}
		
		//Third edge
		k = c3x*e3x + c3y*e3y;
		
		if (k > 0){
			double len = e3x*e3x + e3y*e3y;
			
			if (k < len){
				if (c3sqr * len <= k*k)
					return true;
			}
		}
		
		//We're done, no intersection
		return false;
	}
	/**return an array of rgb components from hex string, welcome to Oddwarg's Efficiency Hell!*/
	public static int[] getColorHex(String hex){
		char[] chars = hex.toCharArray();
		int index = chars[0]=='#'?1:0;
		return new int[]{
			(chars[index+0]<65?chars[index+0]&(0xF):9+chars[index+0]&(0xF))<<4 | (chars[index+1]<65?chars[index+1]&(0xF):9+chars[index+1]&(0xF)),
			(chars[index+2]<65?chars[index+2]&(0xF):9+chars[index+2]&(0xF))<<4 | (chars[index+3]<65?chars[index+3]&(0xF):9+chars[index+3]&(0xF)),
			(chars[index+4]<65?chars[index+4]&(0xF):9+chars[index+4]&(0xF))<<4 | (chars[index+5]<65?chars[index+5]&(0xF):9+chars[index+5]&(0xF))
		};
	}
	
	/**generate a 4byte ARGB BufferedImage*/
	public static BufferedImage createByteABGRCopy(Image img) {
		BufferedImage bi = new BufferedImage(img.getWidth(null),img.getHeight(null),BufferedImage.TYPE_4BYTE_ABGR);
		Graphics g = bi.createGraphics();
		g.drawImage(img,0,0,null);
		g.dispose();
		return bi;
	}
	
	/**generate a 4byte ARGB BufferedImage, splitting the strip into num frames*/
	public static BufferedImage[] createByteABGRFrames(Image img,int num) {
		BufferedImage[] bi = new BufferedImage[num];
		for(int i=0; i<num; i++){
			bi[i] = new BufferedImage(img.getWidth(null)/num,img.getHeight(null),BufferedImage.TYPE_4BYTE_ABGR);
			Graphics g = bi[i].createGraphics();
			g.drawImage(img,-i*img.getWidth(null)/num,0,null);
			g.dispose();
		}
		return bi;
	}
	/*END*/
	
	
	/**Convert radians to degrees
	 * The toDeg constant may be used instead.*/
	public static double toDeg(double radians)
	{
		return 180*radians/Math.PI;
	}
	/**Convert degrees to radians
	 * The toRad constant may be used instead.*/
	public static double toRad(double degrees)
	{
		return Math.PI*degrees/180;
	}
	/**Calculate the distance from the origin to (x,y)*/
	public static double dist(double x, double y)
	{
		return Math.sqrt(x*x+y*y);
	}
	
	/**Calculate the squared distance from the origin to (x,y) (cheap)*/
	public static double sqDist(double x, double y)
	{
		return x*x+y*y;
	}
	/**Calculate the distance from the (x1,y1) to (x2,y2)*/
	public static double dist(double x1,double y1,double x2,double y2)
	{
		return Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
	}
	/**Calculate the distance from the origin to (x,y,z)*/
	public static double dist(double x,double y,double z)
	{
		return Math.sqrt(x*x+y*y+z*z);
	}
	/**Calculate the distance from the (x1,y1,z1) to (x2,y2,z2)*/
	public static double dist(double x1,double y1,double z1,double x2,double y2,double z2)
	{
		return Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)+(z2-z1)*(z2-z1));
	}
	/**Compute a rather accurate approximation to euclidian distance, using fast integer arithmetic.*/
	public static int approxIntegerDistance(int dx, int dy)
	{
		long min, max, approx;
		
		if ( dx < 0 ) dx = -dx;
		if ( dy < 0 ) dy = -dy;
		
		if ( dx < dy )
		{
			min = dx;
			max = dy;
		} 
		else 
		{
			min = dy;
			max = dx;
		}
		
		approx = ( max * 1007 ) + ( min * 441 );
		if ( max < ( min << 4 ))
			approx -= ( max * 40 );
		
		// add 512 for proper rounding
		return (int)(( approx + 512 ) >> 10 );
	}
	/**
	 * Calculate the direction from (x1,y1) to (x2,y2)
	 */
	public static double dir(double x1, double y1, double x2, double y2)
	{
		double dx = x2-x1;
		double dy = y2-y1;
		double dist = dist(dx,dy);
		dx/=dist;
		dy/=dist;
		if(dx==0 && dy==0)
			return 0;
		if(dx>=0 && dy<=0)
		{
			dy*=-1;
			return Math.atan(dy/dx);
		}
		if(dx<0 && dy<=0)
		{
			dx*=-1;
			dy*=-1;
			return Math.PI-Math.atan(dy/dx);
		}
		if(dx>=0 && dy>0)
		{
			return 2*Math.PI-Math.atan(dy/dx);
		}
		if(dx<0 && dy>0)
		{
			dx*=-1;
			return Math.PI+Math.atan(dy/dx);
		}
		return 0;
	}
	/**Calculate the direction from (x1,y1) to (x2,y2)*/
	public static double dir(int x1, int y1, int x2, int y2)
	{
		return dir((double)x1,(double)y1,(double)x2,(double)y2);
	}
	/**Approximation to the sine. Up to 25% faster than Math.cos.*/
	public static float fastSin(float angle)
	{
		return fastCos(PI/2-angle);
	}
	/**Approximation to the cosine. Up to 25% faster than Math.cos.*/
	public static float fastCos(final float angle)
	{
		final float z = cyclic(2f*angle/PI, 4f);
		if(z < 1f)
			return fc(z);
		else if(z < 2f) 
			return -fc(2f-z);
		else if(z < 3f)
			return -fc(z-2f);
		else
			return fc(4f-z);
	}
	private static float fc(final float z)
	{
		return 1f-z*z*((2f-PI/4)-z*z*(1f-PI/4f));
	}
	
	/**Force the given number into the interval by adding or subtracting the size of the range*/
	public static int cyclic(int number,int min, int max)
	{
		number = (number-min)%(max-min);
		if (number<0) number+=(max-min);
		return number+min;
	}
	/**Force the given number into the interval by adding or subtracting the size of the range*/
	public static double cyclic(double number,double min, double max)
	{
		number = (number-min)%(max-min);
		if (number<0) number+=(max-min);
		return number+min;
	}
	/**Force the given number into the interval by adding or subtracting the size of the range. Min is implicitly 0.*/
	public static int cyclic(int number, int max)
	{
		return (number % max + max) % max;
	}
	/**Force the given number into the interval by adding or subtracting the size of the range. Min is implicitly 0.*/
	public static float cyclic(float number, float max)
	{
		return (number % max + max) % max;
	}
	/**Calculate the shortest difference(never above Math.PI, never below -Math.PI) between any 2 angles*/
	public static double dirDiff(double dir1, double dir2)
	{
		double diff = dir2-dir1;
		while (diff<-Math.PI)
			diff+=2*Math.PI;
		while (diff>Math.PI)
			diff-=2*Math.PI;
		return diff;
	}
	/**
	 * Normalize a float array(as if it were a mathematical vector)
	 * @param vector the vector to be normalized
	 * @return the same array as the input, but now normalized. (The reference is identical to the input) 
	 */
	public static float[] normalize(float[] vector)
	{
		float length = 0;
		//vector = vector.clone();??
		for(int i=0; i<vector.length; i++)
			length+=Math.pow(vector[i],2);
		length=(float) Math.sqrt(length);
		for(int i=0; i<vector.length; i++)
			vector[i]/=length;
		return vector;
	}
	/**Create a new vector which is the cross product a x b*/
	public static float[] cross(float[] a, float[] b)
	{
		float x,y,z;
		x=a[1]*b[2]-a[2]*b[1];
		y=a[2]*b[0]-a[0]*b[2];
		z=a[0]*b[1]-a[1]*b[0];
		return new float[]{x,y,z};
	}
	/**
	 * @param src The vector to scale
	 * @param multiplier The scale factor
	 * @return The src vector
	 */
	public static float[] multiply(float[] src, float multiplier)
	{
		for(int i = 0; i<src.length; i++)
			src[i] *= multiplier;
		return src;
	}
	/**
	 * Add two vectors(same size) with multipliers
	 */
	public static float[] add(float[] v1, float m1, float[] v2, float m2)
	{
		float[] r = new float[v1.length];
		for(int i=0; i<r.length; i++)
		{
			r[i] = v1[i]*m1+v2[i]*m2;
		}
		return r;
	}
	/**
	 * Add two vectors(same size) with a floating point multiplier for the last one
	 */
	public static float[] add(float[] v1, float[] v2, float m2)
	{
		float[] r = new float[v1.length];
		for(int i=0; i<r.length; i++)
		{
			r[i] = v1[i]+v2[i]*m2;
		}
		return r;
	}
	/**Create a concatenated X*Y*Z euler rotation matrix, putting the result in the indicated destination
	 * Optional y-mirroring*/
	public static void makeXYZMatrixOpt(float rX,float rY,float rZ, boolean mirror, float[][] destination)
	{
		//generate units
		float cx = (float) Math.cos(rX);
		float sx = (float) Math.sin(rX);
		float cy = (float) Math.cos(rY);
		float sy = (float) Math.sin(rY);
		float cz = (float) Math.cos(rZ);
		float sz = (float) Math.sin(rZ);
		if(mirror) {sy*=-1; sz*=-1;}
		destination[0][0] = cy*cz;
		destination[0][1] = -cy*sz;
		destination[0][2] = sy;
		destination[1][0] = cx*sz + sy*cz*sx;
		destination[1][1] = cx*cz - sx*sy*sz;
		destination[1][2] = - sx*cy;
		destination[2][0] = sx*sz - sy*cz*cx;
		destination[2][1] = sx*cz + cx*sy*sz;
		destination[2][2] = cx*cy;
	}
	/**Create a concatenated X*Y*Z euler rotation matrix, allocating the result in a new matrix
	 * Optional y-mirroring*/
	public static float[][] makeXYZMatrix(float rX,float rY,float rZ, boolean mirror)
	{
		//generate units
		float cx = (float) Math.cos(rX);
		float sx = (float) Math.sin(rX);
		float cy = (float) Math.cos(rY);
		float sy = (float) Math.sin(rY);
		float cz = (float) Math.cos(rZ);
		float sz = (float) Math.sin(rZ);
		if(mirror) {sy*=-1; sz*=-1;}
		
		float[][] destination = new float[3][3];
		destination[0][0] = cy*cz;
		destination[0][1] = -cy*sz;
		destination[0][2] = sy;
		destination[1][0] = cx*sz + sy*cz*sx;
		destination[1][1] = cx*cz - sx*sy*sz;
		destination[1][2] = - sx*cy;
		destination[2][0] = sx*sz - sy*cz*cx;
		destination[2][1] = sx*cz + cx*sy*sz;
		destination[2][2] = cx*cy;
		return destination;
		/*float[][] rx = new float[][]{
					{1,0,0},
					{0,cx,-sx},
					{0,sx,cx}
				};
		float[][] ry = new float[][]{
					{cy,0,sy},
					{0,1,0},
					{-sy,0,cy}
				};
		float[][] rz = new float[][]{
					{cz,-sz,0},
					{sz,cz,0},
					{0,0,1}
				};
		return matrixMultiply3(rz,matrixMultiply3(ry,rx));*/
	}
	
	public static double log2(double d)
	{
		return Math.log(d)/Math.log(2);
	}
	
	public static float[][] makeZMatrix(float rZ)
	{
		float cz = (float) Math.cos(-rZ);
		float sz = (float) Math.sin(-rZ);
		
		return new float[][]{
			{cz,-sz, 0},
			{sz, cz, 0},
			{0,  0,  1}
		};
	}
	
	public static float[][] makeXMatrix(float rX)
	{
		float cz = (float) Math.cos(-rX);
		float sz = (float) Math.sin(-rX);
		
		return new float[][]{
			{1, 0,  0},
			{0, cz,-sz},
			{0, sz, cz}
		};
	}
	
	public static float[][] makeYMatrix(float rY)
	{
		float cz = (float) Math.cos(-rY);
		float sz = (float) Math.sin(-rY);
		
		return new float[][]{
			{ cz, 0, sz},
			{ 0,  1, 0},
			{-sz, 0, cz}
		};
	}
	
	/**
	 * Postmultiply a float[3] to a float[3][3], return a new, resulting float[3]
	 */
	public static float[] rotationMatrixPostMultiply(float[][] m, float[] v)
	{
		return new float[]{
			v[0]*m[0][0]+v[1]*m[0][1]+v[2]*m[0][2],
			v[0]*m[1][0]+v[1]*m[1][1]+v[2]*m[1][2],
			v[0]*m[2][0]+v[1]*m[2][1]+v[2]*m[2][2]
		};
	}
	/**
	 * Postmultiply a float[3] to a float[3][3], replacing the contents of the vector.
	 * The matrix is unchanged.
	 */
	public static void rotationMatrixPostMultiplyOpt(float[][] m, float[] v)
	{
		float x=v[0];
		float y=v[1];
		float z=v[2];
		v[0]=x*m[0][0]+y*m[0][1]+z*m[0][2];
		v[1]=x*m[1][0]+y*m[1][1]+z*m[1][2];
		v[2]=x*m[2][0]+y*m[2][1]+z*m[2][2];
	}
	/**
	 * Postmultiply a double[3] to a float[3][3], replacing the contents of the vector.
	 * The matrix is unchanged.
	 */
	public static void rotationMatrixPostMultiplyOpt(float[][] m, double[] v)
	{
		double x=v[0];
		double y=v[1];
		double z=v[2];
		v[0]=x*m[0][0]+y*m[0][1]+z*m[0][2];
		v[1]=x*m[1][0]+y*m[1][1]+z*m[1][2];
		v[2]=x*m[2][0]+y*m[2][1]+z*m[2][2];
	}
	/**
	 * Postmultiply a float[3] to a float[9], replacing the contents of the vector.
	 * The matrix is unchanged.
	 */
	public static void rotationMatrixPostMultiplyOpt(float[] m, float[] v)
	{
		float x=v[0];
		float y=v[1];
		float z=v[2];
		v[0]=x*m[0]+y*m[1]+z*m[2];
		v[1]=x*m[3]+y*m[4]+z*m[5];
		v[2]=x*m[6]+y*m[7]+z*m[8];
	}
	/**
	 * Premultiply a float[3] to a float[3][3], return a new, resulting float[3]
	 */
	public static float[] rotationMatrixPreMultiply(float[] v,float[][] m)
	{
		return new float[]{
			v[0]*m[0][0]+v[1]*m[1][0]+v[2]*m[2][0],
			v[0]*m[0][1]+v[1]*m[1][1]+v[2]*m[2][1],
			v[0]*m[0][2]+v[1]*m[1][2]+v[2]*m[2][2]
		};
	}
	
	/**Multiply the matrices m1 x m2, putting the result in m1*/
	public static void matrixMultiply3OptFirst(float[][]m1, float[][]m2)
	{
		float m100=m1[0][0],m101=m1[0][1],m102=m1[0][2];
		float m110=m1[1][0],m111=m1[1][1],m112=m1[1][2];
		float m120=m1[2][0],m121=m1[2][1],m122=m1[2][2];
		
		m1[0][0]=m100*m2[0][0]+m101*m2[1][0]+m102*m2[2][0];
		m1[0][1]=m100*m2[0][1]+m101*m2[1][1]+m102*m2[2][1];
		m1[0][2]=m100*m2[0][2]+m101*m2[1][2]+m102*m2[2][2];
		
		m1[1][0]=m110*m2[0][0]+m111*m2[1][0]+m112*m2[2][0];
		m1[1][1]=m110*m2[0][1]+m111*m2[1][1]+m112*m2[2][1];
		m1[1][2]=m110*m2[0][2]+m111*m2[1][2]+m112*m2[2][2];
		
		m1[2][0]=m120*m2[0][0]+m121*m2[1][0]+m122*m2[2][0];
		m1[2][1]=m120*m2[0][1]+m121*m2[1][1]+m122*m2[2][1];
		m1[2][2]=m120*m2[0][2]+m121*m2[1][2]+m122*m2[2][2];
	}
	
	/**Multiply the matrices m1 x m2, putting the result in m2*/
	public static void matrixMultiply3OptLast(float[][]m1, float[][]m2)
	{
		float m200=m2[0][0],m201=m2[0][1],m202=m2[0][2];
		float m210=m2[1][0],m211=m2[1][1],m212=m2[1][2];
		float m220=m2[2][0],m221=m2[2][1],m222=m2[2][2];
		
		m2[0][0]=m1[0][0]*m200+m1[0][1]*m210+m1[0][2]*m220;
		m2[0][1]=m1[0][0]*m201+m1[0][1]*m211+m1[0][2]*m221;
		m2[0][2]=m1[0][0]*m202+m1[0][1]*m212+m1[0][2]*m222;
		
		m2[1][0]=m1[1][0]*m200+m1[1][1]*m210+m1[1][2]*m220;
		m2[1][1]=m1[1][0]*m201+m1[1][1]*m211+m1[1][2]*m221;
		m2[1][2]=m1[1][0]*m202+m1[1][1]*m212+m1[1][2]*m222;
		
		m2[2][0]=m1[2][0]*m200+m1[2][1]*m210+m1[2][2]*m220;
		m2[2][1]=m1[2][0]*m201+m1[2][1]*m211+m1[2][2]*m221;
		m2[2][2]=m1[2][0]*m202+m1[2][1]*m212+m1[2][2]*m222;
	}
	
	public static float[][] matrixMultiply3(float[][]m1, float[][]m2)
	{
		return new float[][]{
			{m1[0][0]*m2[0][0]+m1[0][1]*m2[1][0]+m1[0][2]*m2[2][0],m1[0][0]*m2[0][1]+m1[0][1]*m2[1][1]+m1[0][2]*m2[2][1],m1[0][0]*m2[0][2]+m1[0][1]*m2[1][2]+m1[0][2]*m2[2][2]},
			{m1[1][0]*m2[0][0]+m1[1][1]*m2[1][0]+m1[1][2]*m2[2][0],m1[1][0]*m2[0][1]+m1[1][1]*m2[1][1]+m1[1][2]*m2[2][1],m1[1][0]*m2[0][2]+m1[1][1]*m2[1][2]+m1[1][2]*m2[2][2]},
			{m1[2][0]*m2[0][0]+m1[2][1]*m2[1][0]+m1[2][2]*m2[2][0],m1[2][0]*m2[0][1]+m1[2][1]*m2[1][1]+m1[2][2]*m2[2][1],m1[2][0]*m2[0][2]+m1[2][1]*m2[1][2]+m1[2][2]*m2[2][2]}
		};
	}
	
	public static float[] multMatrixFlat4x4(float[] left, float[] right) 
	{
		float[] tmp = new float[16];
		
		for (int i = 0; i < 4; i++) 
		{
			tmp[i*4+0] =
				(left[i*4+0] * right[0*4+0]) +
				(left[i*4+1] * right[1*4+0]) +
				(left[i*4+2] * right[2*4+0]) +
				(left[i*4+3] * right[3*4+0]) ;
			
			tmp[i*4+1] =
				(left[i*4+0] * right[0*4+1]) +
				(left[i*4+1] * right[1*4+1]) +
				(left[i*4+2] * right[2*4+1]) +
				(left[i*4+3] * right[3*4+1]) ;
			
			tmp[i*4+2] =
				(left[i*4+0] * right[0*4+2]) +
				(left[i*4+1] * right[1*4+2]) +
				(left[i*4+2] * right[2*4+2]) +
				(left[i*4+3] * right[3*4+2]) ;
			
			tmp[i*4+3] =
				(left[i*4+0] * right[0*4+3]) +
				(left[i*4+1] * right[1*4+3]) +
				(left[i*4+2] * right[2*4+3]) +
				(left[i*4+3] * right[3*4+3]) ;
		}
		return tmp;
	}
	
	/**
	 * Parses a string to an array of floats. Must be separated with whitespaces.
	 */
	public static float[] getFloatArray(String line)
	{
		String[] split = line.split(" ");
		float[] c = new float[split.length];
		for(int i=0; i<split.length; i++)
		{
			c[i] = Float.parseFloat(split[i]);
		}
		return c;
	}
	
	public static int countOccurrences(String haystack, char needle)
	{
		int count = 0;
		for (int i=0; i < haystack.length(); i++)
		{
			if (haystack.charAt(i) == needle)
			{
				count++;
			}
		}
		return count;
	}
	
	public static double mirror(double d, boolean mirror)
	{
		return d*(mirror?-1:1);
	}
	@SafeVarargs
	public static<T> T chooseString(T... strings)
	{
		return strings[(int)(strings.length*Math.random())];
	}
	public static float[][] transpose3(float[][] a)
	{
		return new float[][]{
			{a[0][0],a[1][0],a[2][0]},
			{a[0][1],a[1][1],a[2][1]},
			{a[0][2],a[1][2],a[2][2]}};
	}
	/**Force the number into the bounds*/
	public static double limit(double number, double minimum, double maximum)
	{
		if (number<minimum)
			return minimum;
		if (number>maximum)
			return maximum;
		return number;
	}
	/**Force the numbers in the array into the bounds
	 * @return the array itself*/
	public static float[] limit(float[] values, float minimum, float maximum)
	{
		for(int i = 0; i<values.length; i++)
		{
			if (values[i]<minimum)
				values[i] = minimum;
			else if (values[i]>maximum)
				values[i] = maximum;
		}
		return values;
	}
	/**Force the number into the bounds*/
	public static float limit(float number, float minimum, float maximum)
	{
		if (number<minimum)
			return minimum;
		if (number>maximum)
			return maximum;
		return number;
	}
	/**Force the number into the bounds [minimum, maximum>*/
	public static int limit(int number, int minimum, int maximum)
	{
		if (number<minimum)
			return minimum;
		if (number>=maximum)
			return maximum-1;
		return number;
	}
	
	/**Force the number into the bounds.
	 * @param clamped A byte array where we will increment a value if the number was clamped. It is left unaltered otherwise.
	 * @param index The index to use in the byte array.*/
	public static double limit(double number, double minimum, double maximum, byte[] clamps, byte index)
	{
		if (number<minimum)
		{
			clamps[index]++;
			return minimum;
		}
		if (number>maximum)
		{
			clamps[index]++;
			return maximum;
		}
		return number;
	}
	
	/**Failsafe version of arccos*/
	public static double acos(double d)
	{
		if (d<=-1)
			return  Math.PI;
		else if (d>=1)
			return  0;
		return Math.acos(d);
	}
	
	public static float[][] makeEulerMatrix(float[] r, float f)
	{
		float c = (float)Math.cos(f);
		float s = (float)Math.sin(f);
		float[][] m = new float[][]{
			{c+r[0]*r[0]*(1-c)		,r[0]*r[1]*(1-c)-r[2]*s	,r[0]*r[2]*(1-c)+r[1]*s },
			{r[1]*r[0]*(1-c)+r[2]*s	,c+r[1]*r[1]*(1-c)		,r[1]*r[2]*(1-c)-r[0]*s	},
			{r[2]*r[0]*(1-c)-r[1]*s	,r[2]*r[1]*(1-c)+r[0]*s	,c+r[2]*r[2]*(1-c)		}};
		return m;
	}
	/**Deeper cloning of 2D array*/
	public static float[][] clone2D(float[][] src)
	{
		float[][] result = new float[src.length][];
		for(int i=0; i<result.length; i++)
		{
			result[i] = src[i].clone();
		}
		return result;
	}
	/**Manhattan distance*/
	public static double manDist(double x1, double y1, double x2, double y2)
	{
		return Math.abs(x2-x1)+Math.abs(y2-y1);
	}
	public static void fill(float[] array, float a,float b,float c,float d)
	{
		array[0]=a;
		array[1]=b;
		array[2]=c;
		array[3]=d;
	}
	public static double min(double a, double b, double c)
	{
		if(a<=b && a<=c)
			return a;
		else if (b<=c)
			return b;
		return c;
	}
	public static double max(double a, double b, double c)
	{
		if(a>=b && a>=c)
			return a;
		else if (b>=c)
			return b;
		return c;
	}
	public static float min(float a, float b, float c)
	{
		if(a<=b && a<=c)
			return a;
		else if (b<=c)
			return b;
		return c;
	}
	public static float max(float a, float b, float c)
	{
		if(a>=b && a>=c)
			return a;
		else if (b>=c)
			return b;
		return c;
	}
	
	public static float min(float...fs)
	{
		float min = fs[0];
		for(int i = 1; i<fs.length; i++)
		{
			if(fs[i] < min)
				min = fs[i];
		}
		return min;
	}
	
	public static float max(float...fs)
	{
		float max = fs[0];
		for(int i = 1; i<fs.length; i++)
		{
			if(fs[i] > max)
				max = fs[i];
		}
		return max;
	}
	/**Compute SHA-1 hash
	 * @throws NoSuchAlgorithmException If there is no SHA-1 algorithm on the system.*/
	public static String SHAsum(byte[] convertme) throws NoSuchAlgorithmException 
	{
		MessageDigest md = MessageDigest.getInstance("SHA-1");
		return new String(md.digest(convertme));
	}
	/**Write the RGBA byte data as a png.*/
	public static void writeBytePng(String fname, int width, int height, byte[] data)
	{
		BufferedImage b = new BufferedImage(width,height,BufferedImage.TYPE_4BYTE_ABGR);
		b.getRaster().setDataElements(0, 0, width, height, data);
		try
		{ImageIO.write(b, "PNG", new File(fname));}
		catch (IOException e)
		{e.printStackTrace();}
	}
	
	/**Strip the extension if it exists*/
	public static String stripExtension(String fname)
	{
		int i = fname.lastIndexOf('.');
		if(i==-1)
			return fname;
		return fname.substring(0, i);
	}
	/**Get a class by its simple name, by searching the project's packages.*/
	public Class<?> getClassByName(String className) throws ClassNotFoundException
	{
		Class<?> result = null;
		Package[] packages = Package.getPackages();
		for(Package p : packages)
		{
			try
			{
				result = Class.forName(p.getName()+'.'+className);
				break;
			}
			catch (ClassNotFoundException e)
			{}
		}
		if(result==null)
			throw new ClassNotFoundException("There is no class called "+className);
		return result;
	}
	
	/**Returns the extension, without the dot, in lower case, or the empty string if it does not exist.*/
	public static String getExtension(String name)
	{
		int dot = name.lastIndexOf('.');
		String extension;
		if(dot==-1)
			extension = "";
		else
			extension = name.substring(dot+1, name.length()).toLowerCase();
		return extension;
	}
	
	public static byte[] IntToBytes(int value)
	{
		return new byte[]{(byte)((value&0xFF000000)>>>24),(byte)((value&0x00FF0000)>>>16),(byte)((value&0x0000FF00)>>8),(byte)(value&0x000000FF)};
	}
	
	public static int BytesToInt(byte[] value)
	{
		return ((value[0]&0xFF)<<24) | ((value[1]&0xFF)<<16) | ((value[2]&0xFF)<<8) | ((value[3]&0xFF));
	}
	/**When invoked, this method will multiply each pair of elements in the 4-element arrays.
	 * The result is stored in dstValue(the first array).*/
	public static void multiplyEach4f(float[] dstValue, float[] multiplier)
	{
		dstValue[0] *= multiplier[0];
		dstValue[1] *= multiplier[1];
		dstValue[2] *= multiplier[2];
		dstValue[3] *= multiplier[3];
	}
	
	public static void println(Object... args)
	{
		for(int i=0; i<args.length-1; i++)
		{
			System.out.print(args[i]+", ");
		}
		if(args.length>0)
			System.out.println(args[args.length-1]);
	}
	public static boolean passed(float previous, float current, float value)
	{
		return current >= value && previous < value;
	}
	/**Returns a value that increases and decreases between 0 and max, at the same pace as the value.*/
	public static float patrol(float value, float max)
	{
		float bar = value%max;
		if((int)(value/max)%2 == 0)
			return bar;
		else
			return max-bar;
	}
	/**Returns a value that increases and decreases between 0 and max, at the same pace as the value.*/
	public static int patrol(int value, int max)
	{
		int bar = value%max;
		if((int)(value/max)%2 == 0)
			return bar;
		else
			return max-bar;
	}
	
	/**Filter the array on the given regex. Returns a new array that contains each element from the original list if and only if
	 * the element matches the regex, that is list[j] is retained iff list[j].matches(regex).
	 * If regex is null, the original reference to the list is returned.*/
	public static String[] filter(String[] list, String regex)
	{
		if(regex == null)
			return list;
		ArrayList<String> matches = new ArrayList<String>();
		for(String s : list)
		{
			if(s.matches(regex))
				matches.add(s);
		}
		String[] result = new String[matches.size()];
		matches.toArray(result);
		return result;
	}
	/**
	 * @param start The lowermost value to put in the list, inclusive
	 * @param end The upper bound of values to put in the list, exclusive
	 * @return A list containing integers from start to end-1, inclusive
	 */
	public static ArrayList<Integer> getCountingList(int start, int end)
	{
		int size = end-start;
		ArrayList<Integer> result = new ArrayList<Integer>(size);
		for(int i = start; i<end; i++)
			result.add(i);
		return result;
	}
	
	/**
	 * @param start The lowermost value to put in the list, inclusive
	 * @param end The upper bound of values to put in the list, exclusive
	 * @return An array containing integers from start to end-1, inclusive
	 */
	public static LinkedHashSet<Integer> getCountingSet(int start, int end)
	{
		int size = end-start;
		LinkedHashSet<Integer> result = new LinkedHashSet<Integer>(size);
		for(int i = start; i<end; i++)
			result.add(i);
		return result;
	}
	/**
	 * @param start The lowermost value to put in the list, inclusive
	 * @param end The upper bound of values to put in the list, exclusive
	 * @return An array containing integers from start to end-1, inclusive
	 */
	public static int[] getCountingArray(int start, int end)
	{
		int size = end-start;
		int[] result = new int[size];
		for(int i = 0; i<size; i++)
			result[i] = start+i;
		return result;
	}
	public static double absMax(double value, double minimum)
	{
		if(value>=0)
			return Math.max(value, minimum);
		else
			return Math.min(value, -minimum);
	}
	/**@return boy==null?girl==null:boy.equals(girl)*/
	public static boolean equals(Object boy, Object girl)
	{
		if(boy == null)
			return girl == null;
		else
			return boy.equals(girl);
	}
	/**Returns the first index of the item in the list of weak references, or -1 if it was not found.
	 * @see ArrayList#indexOf(Object)*/
	public static<T> int indexOfWeakReference(ArrayList<WeakReference<T>> list, T item)
	{
		for(int i = 0; i<list.size(); i++)
		{
			if(		(item == null)?
				(list.get(i) == null || list.get(i).get() == null)
				:
					item.equals(list.get(i).get()))
				return i;
		}
		return -1;
	}
	public static float[] toFloat(int hexColor)
	{
		float[] color = new float[4];
		color[3] = 1.0f;
		setHexColor(color, hexColor);
		return color;
	}
	public static void setHexColor(float[] color, int hexColor)
	{
		color[0] = (float)((hexColor&0xFF0000)>>16)/0xFF;
		color[1] = (float)((hexColor&0x00FF00)>> 8)/0xFF;
		color[2] = (float)((hexColor&0x0000FF)>> 0)/0xFF;
	}
	/**Returns the powerth power of the absolute value of the number, multiplied by the sign of the number.<br/>
	 * Example: signedPow(-3, 2) returns -9*/
	public static double signedPow(double number, double power)
	{
		if(number < 0)
			return -Math.pow(-number, power);
		else
			return Math.pow(number, power);
	}
	/**
	 * If the absolute value of the input value is smaller than absoluteMinimum, 
	 * then the method returns absoluteMinimum multiplied by the sign of the value.
	 * Otherwise, the value itself is returned.<br/>
	 * This is ideal to prevent division by zero, for example: <br/>
	 * 1f/signedMax(divisor, 1) will divide by 1 or -1 rather than dividing by very small numbers around zero
	 * @param value The number to evaluate
	 * @param absoluteMinimum A positive threshold for the smallest permitted absolute value
	 * @return A number with the same sign as the value, whose absoluite value is at least the absoluteMinimum
	 */
	public static float signedMax(float value, float absoluteMinimum)
	{
		if(value <= absoluteMinimum || value >= -absoluteMinimum)
			return value;
		return value>=0?absoluteMinimum:-absoluteMinimum;
	}
	public static String[] listFileNames(String folderPath, boolean files, boolean folders)
	{
		File folder = new File(folderPath);
		if (!folder.isDirectory())
			throw new IllegalArgumentException(folderPath+" is not a folder!");
		
		ArrayList<String> subFolders = new ArrayList<String>();
		for (File f : folder.listFiles())
		{
			if(f.isDirectory()?folders:files)
				subFolders.add(f.getName());
		}
		String[] r = new String[subFolders.size()];
		subFolders.toArray(r);
		return r;
	}
	/**Directly generate a random 32 bit float number using a {@link java.util.Random} instance.*/
	public static float random()
	{
		return rng.nextFloat();
	}
	/**Same as Math.sqrt but automatic cast to float.*/
	public static float sqrt(float f)
	{
		return (float)Math.sqrt(f);
	}
	/**This function returns an approximation of the square root of a 32 bit float.
	 * It can only guarantee 1 decimal digit of precision, but is about 24% faster than Math.sqrt.*/
	public static float fastSqrt(float f)
	{
		return Float.intBitsToFloat((Float.floatToIntBits(f) + (127<<23)) >>> 1);
		//Note: applying newton's method gains accuracy but nullifies the performance gain.
	}
	
	public static String readFileString(InputStream s) throws IOException {
		StringBuilder sb = new StringBuilder(256);
		Reader r = new InputStreamReader(s);
		BufferedReader br = new BufferedReader(r);
		String in;
		while((in = br.readLine())!=null) {
			sb.append(in);
			sb.append('\n');
		}
		s.close();
		return sb.toString();
	}
	
	public static String toString(Object... args)
	{
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<args.length-1; i++)
		{
			sb.append(args[i]);
			sb.append(", ");
		}
		if(args.length>0)
			sb.append(args[args.length-1]);
		return sb.toString();
	}
	
	public static Rectangle intersection(Rectangle a, Rectangle b)
	{
		Rectangle dst = new Rectangle(Math.max(a.x, b.x), Math.max(a.y, b.y), 0, 0);
		dst.width = Math.max(0, Math.min(a.x+a.width, b.x+b.width)-dst.x);
		dst.height = Math.max(0, Math.min(a.y+a.height, b.y+b.height)-dst.y);
		return dst;
	}
}
